CS254 Spring 2017Practice Final

Studying for one of my tests does involve some memorization. I believe this is an important skill. Often people waste a lot of time and fail to remember the things they are trying to memorize. Please use a technique that has been shown to work such as the method of loci. Other memorization techniques can be found off the Wiki Page for Moonwalking with Einstein. Given this, to study for the midterm, I suggest you:

• Know how to do (by heart) all the practice problems.
• Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
• Go over the homework problems.
• Try to create your own problems similar to the ones I have given and solve them.
• If you want to study in groups, at this point you are ready to quiz each other.

Here are some facts about the actual final:

1. It is comprehensive covering all the material of the semester.
2. It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test.
3. You should bring photo ID.
4. There will be more than one version of the test. Each version will be of comparable difficulty.
5. It is 10 problems, 6 problems will be on material since the midterm, four problems will come from the topics covered prior to the midterm.
6. Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm.

The practice final is below:

1. Show the language `{langle i,x,y\rangle | \mbox{the }i\mbox{th bit of }x \cdot y \mbox{ is } 1 }` is in L. (Here L is logspace).
2. Prove `PATH in SPACE(log^2 n)`.
3. Prove `SPACE(n) != NP`.
4. Prove `\cup_k \Sigma_2-TIME(n^k) = NP^{NP}`.
5. Give the claims that were needed to show `SAT !in TISP(n^{1.1},n^{0.1})`
6. Give an `NC^1` circuit family for the language `{x \in {0,1}^n | \quad x \mbox{ at least 5 of } x\mbox{'s bits are } 1}}`
7. Define or give the algorithm for (a) the class BPP, (b) canonical derandomization, (c) WalkSat.
8. Explain how Chernoff bounds can be used to reduce the error rate of any BPP algorithm. If one has bounded-error probabilistic algorithm with bounded error `1/2+1/n^c`, how many repetitions are needed to reduce the error to `1/2^{n}`?
9. Give the Set Lower Bound protocol and explain some uses that we have had for it in CS 254.
10. Prove that for any fixed `k` there is a language in `Sigma_2^p` that is not computed by a circuit family of size `n^k`.